/**
 * @file binarytree.h
 * @author 冯皓 
 * @brief 
 * @version 0.1
 * @date 2022-11-04
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
#include <algorithm>
using namespace std;
template <typename Comparable>
class Node
{
protected:
    Comparable element;
public:
    virtual Comparable get(){return element;}
    virtual void set(Comparable _val){element = _val;}
    Node(Comparable _val){element = _val;}
};
template <typename Comparable>
/**
 * @brief 一般二叉树的结点
 * 
 */
class BinaryNode:public Node<Comparable>{
protected:
    Comparable element;
    BinaryNode *left;
    BinaryNode *right;
    BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
    : element{ theElement }, left{ lt }, right{ rt } { }
    BinaryNode( Comparable && theElement, BinaryNode *lt, BinaryNode *rt )
    : element{ std::move( theElement ) }, left{ lt }, right{ rt } { };
};
/**
 * @brief avl树的结点
 * 
 * @tparam Comparable 
 */
template <typename Comparable>
class AvlNode:public BinaryNode <Comparable>{
protected:
    int height;
    AvlNode( const Comparable & ele, AvlNode *lt, AvlNode *rt, int h = 0 )
    : BinaryNode<Comparable>{ele,lt,rt}, height{ h } { }
    AvlNode( Comparable && ele, AvlNode *lt, AvlNode *rt, int h = 0 )
    : BinaryNode<Comparable>{ele,lt,rt}, height{ h } { }
};
template <typename Comparable>
class BinaryTree: public BinaryNode <Comparable> {
protected:
    BinaryNode<Comparable>  *root;
public:
    BinaryTree( );
    BinaryTree( const BinaryTree & rhs );
    BinaryTree( BinaryTree && rhs ) ;
    virtual ~BinaryTree( );
    BinaryTree & operator=( const BinaryTree & rhs );
    BinaryTree & operator=( BinaryTree && rhs );
    bool isEmpty( ) const;
    void printTree( ostream & out = cout ) const;
    void makeEmpty( );
    virtual void insert( const Comparable & x );
    virtual void insert( Comparable && x );
    virtual void remove( const Comparable & x );
protected:
    virtual void insert( const Comparable & x, BinaryNode<Comparable> * & t );
    virtual void insert( Comparable && x, BinaryNode<Comparable> * & t );
    virtual void remove( const Comparable & x, BinaryNode<Comparable> * & t );
    bool contains( const Comparable & x, BinaryNode<Comparable> *t ) const;
    void makeEmpty( BinaryNode<Comparable> * & t );
    void printTree( BinaryNode<Comparable> *t, ostream & out ) const;
    BinaryNode<Comparable> * clone( BinaryNode<Comparable> *t ) const;
};
template <typename Comparable>
class BinarySearchTree: public BinaryTree <Comparable>{
public:
    BinarySearchTree( );
    BinarySearchTree( const BinarySearchTree & rhs );
    BinarySearchTree( BinarySearchTree && rhs );
    virtual ~BinarySearchTree( );
    BinarySearchTree & operator=( const BinarySearchTree & rhs );
    BinarySearchTree & operator=( BinarySearchTree && rhs );
    const Comparable & findMin( ) const;
    const Comparable & findMax( ) const;
    virtual void insert( const Comparable & x );
    virtual void insert( Comparable && x );
    virtual void remove( const Comparable & x );
protected:
    virtual void insert( const Comparable & x, BinaryNode<Comparable> * & t );
    virtual void insert( Comparable && x, BinaryNode<Comparable> * & t );
    virtual void remove( const Comparable & x, BinaryNode<Comparable> * & t );
    BinaryNode<Comparable> * findMin( BinaryNode<Comparable> *t ) const;
    BinaryNode<Comparable> * findMax( BinaryNode<Comparable> *t ) const;
};
template <typename Comparable>
class AvlTree: public BinaryTree <Comparable>,public AvlNode <Comparable>{
public:
    AvlTree( );
    AvlTree( const AvlTree & rhs );
    AvlTree( AvlTree && rhs ) ;
    ~AvlTree( );
    AvlTree & operator=( const AvlTree & rhs );
    AvlTree & operator=( AvlTree && rhs );
    virtual void insert( const Comparable & x );
    virtual void insert( Comparable && x );
    virtual void remove( const Comparable & x );
protected:
    AvlNode <Comparable> *root;
    virtual void insert( const Comparable & x, AvlNode<Comparable> * & t );
    virtual void insert( Comparable && x, AvlNode<Comparable> * & t );
    virtual void remove( const Comparable & x, AvlNode<Comparable> * & t );
    void balance( AvlNode<Comparable> * & t );
    int height( AvlNode<Comparable> *t ) const;
    int max( int lhs, int rhs ) const;
    void rotateWithLeftChild( AvlNode<Comparable> * & t );
    void rotateWithRightChild(AvlNode<Comparable> * & t);
    void doubleWithLeftChild(AvlNode<Comparable> * & t);
    void doubleWithRightChild(AvlNode<Comparable> * & t);
};

#endif